\newpage
\begin{center}
\textit{Toutes les mesures qui suivent dans ce rapport ont été
 effectuées sur les machines du Cremi (Salle 203 pour la partie \emph{Pthread},
 et réseau \emph{InfiniBand} pour la partie \emph{MPI}). De plus, les calculs ont été
 effectués sur des matrices de 1024 par 1024 sur 1024 itérations.}
\end{center}

\chapter{Pthread}

\section{Version simple}

Pour la version simple, il nous a fallu instaurer deux barrières (limitée au voisinage)
: une après les recopies de chaque \emph{thread}, et une après le calcul des
voisins. Car en effet, pour le calcul du jeu de la vie, chaque \emph{thread}
est dépendant de l'état de ses voisins en bordure, le calcul
synchronisé des voisins est donc nécessaire pour avancer dans les
itérations. Pour la synchronisation, un seul tableau de sémaphores ne suffit pas, car ces barrières sont indépendantes l'une de l'autre.

Ces deux barrières rajoute de la complexité dans la parallélisation :
\begin{itemize}
\item Nombre augmenté de demande prise de main par les \emph{threads}
\item L'ordonnanceur donne la main à des \emph{threads} en attente d'une
      libération d'un sémaphore.
\end{itemize}

\paragraph{}
Initialement, notre implémentation donnait à chaque
\emph{thread} un travail géré par \textbf{colonne}, en parcourant le portion attribuée
suivant les lignes. Le problème étant qu'à chaque changement de \emph{thread}, le
processeur devait recharger la ligne entière alors que seule une partie
était utilisée par le \emph{thread} courant (correspondant à la largeur d'une
colonne). Cela impliquait donc un rechargement \textit{à chaque fois}
qu'un \emph{thread} changeait de ligne.

\begin{center}
\includegraphics{./img/seq.png}
\end{center}

Nous nous en sommes aperçu, et avons changé la manière de distribuer le
travail, à savoir une \textbf{distribution par ligne}.

\begin{center}
\includegraphics{./img/seq2.png}
\end{center}

Nous avons ensuite comparé les performances, entre les versions
\emph{ligne} et \emph{colonne}, et la différence est bien visible et
loin d'être négligeable.\\

\textbf{Courbes des résultats obtenus :}

\begin{center}
\includegraphics[scale=0.65]{./img/exec_vs.png}

\includegraphics[scale=0.65]{./img/speedup_vs.png}
\end{center}

L'information rendue par la courbe de vitesse d'exécution est
parfaitement logique. Le temps d'exécution diminue grandement de 1 à
8 \emph{threads}, le temps optimal se trouvant autour de 8 (car 8 coeurs dans
la machine). De précédentes prises de mesures montraient aussi qu'à partir
d'un nombre important de \emph{threads} (environ 30), le temps d'exécution
raugmentait au fur et à mesure que le nombre de \emph{thread} était
important. Cela s'explique par la complexité qui réside dans la création
d'un \emph{thread} et des mécanismes de \emph{mutex}. Plus le nombre de \emph{threads} est
important, plus le nombre de demandes de prise de main est important,
augmentant ainsi le temps d'exécution du programme.



 \section{Raffinement}
Le but ici a été de faire en sorte que chaque thread traite ses bordures, préviennent ses voisins, traite ensuite sa portion intérieure, et attende que ses voisins lui transmettent leurs bordures.
Pour cela, nous avons intercalé le code concernant le traitement des zones intérieures entre les appels aux fonctions \texttt{sem\_post} et \texttt{sem\_wait}.

\begin{center}
\includegraphics[scale=0.65]{./img/exec_r.png}

\includegraphics[scale=0.65]{./img/speedup_r.png}
\end{center}

Les courbes ci-dessus n'ont guère de différences avec la version
simple.

\newpage
Voici donc une comparaison plus lisible des deux versions précédentes :

\begin{center}
\includegraphics[scale=0.65]{./img/exec_r_vs.png}

\includegraphics[scale=0.65]{./img/speedup_r_vs.png}
\end{center}

Bien que la différence soit faible, on voit bien que le temps
d'exécution est tout de même inférieur pour la version raffinement,
preuve que les efforts fait à ce niveau n'ont pas été inutiles.
Un travail sur une matrice plus grande aurait peut-être permis de
contraster d'avantage les performances entre les deux versions.



 \section{Stagnation}

\'Etant donné que la charge de travail est la même pour tous les \emph{threads}
(taille des tranches égale), et sachant que le cheminement d'un \emph{thread} est
dépendant de l'état de ses deux voisins, même s'il n'a rien à
faire, il devra tout de même les attendre. Du coup pour que
cette stratégie prenne de l'intérêt, il faut que (par propagation) aucun
des voisins n'ai de travail à faire, cela revient à dire que la matrice
n'évolue plus, et qu'on est donc arrivé au résultat voulu.

La principale différence comparée à la stratégie de raffinement, réside
sur le fait qu'un \emph{thread} attend sans rien faire, au lieu de consommer
des ressources inutilement. Au lieu d'effectuer toutes les instructions
machines correspondantes aux boucles/tests, il attends simplement sur son \texttt{sem\_wait()}.
